package leetcode_day._2022._202202._0110;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/2/10 23:49
 * 最简分数
 * 算法：数学
 * 求两个数的最大公约数是否为 1
 */
public class _10_1447 {

    public List<String> simplifiedFractions(int n) {
        List<String> ans = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
//                if (check(i, j))
                if (gcd1(i, j) == 1)
                    ans.add(j + "/" + i);
            }
        }
        return ans;
    }
    // 暴力 O(n)
    boolean check(int a, int b) {
        for (int i = 2; i <= b; i++) {
            if (a % i == 0 && b % i == 0) return false;
        }
        return true;
    }
    // 欧几里得  O(log(a + b))
    int gcd1(int a, int b) {
        return b == 0 ? a : gcd1(b, a % b);
    }

}
